public class arrangeCoins {
    public static void main(String[] args) {
        System.out.println(arrangeCoins(1000));
        System.out.println(arrangeCoins2(1000));
        System.out.println(arrangeCoins3(1000));
    }

//双指针
    private static int arrangeCoins2(int n) {
        int left = 0 , right = n;
        while(left<=right){
            int mid = (left+right)/2;
            int cost = (mid*mid+mid)/2;
            if(cost==n){
                return mid;
            }else if(cost<n){
                left = mid+1;
            }else {
                right = mid - 1;
            }
        }

        return right;
    }
//牛顿迭代
    private static int arrangeCoins3(int n) {
        if(n == 0 ){
            return 0;
        }


        return (int)sqrt(n,n);

    }

    private static double sqrt(double x,int n) {
        double res = (x+(2*n-x)/x)/2;
        if(res == x){
            return x;
        }else {
            return sqrt(res,n);
        }

    }

    //迭代
    public static int arrangeCoins(int n){
        for(int i=1;i<=n;i++){
            n = n - i;
            if(n<=i){
                return i;
            }
        }
        return 0;
    }

}
